#ifndef STX_ALGORITHM_SET_INTERSECTION_HPP
#define STX_ALGORITHM_SET_INTERSECTION_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class Compare, class InputIterator1, class InputIterator2, class OutputIterator>
inline OutputIterator
set_intersection_impl(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result,
    Compare comp)
{
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            ++first1;
        } else {
            if (!comp(*first2, *first1)) {
                *result = *first1;
                ++result;
                ++first1;
            }
            ++first2;
        }
    }
    return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
inline OutputIterator
set_intersection(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result,
    Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return set_intersection_impl<comp_ref>(first1, last1, first2, last2, result, comp);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
inline OutputIterator
set_intersection(
    InputIterator1 first1,
    InputIterator1 last1,
    InputIterator2 first2,
    InputIterator2 last2,
    OutputIterator result)
{
    return stx::set_intersection(
        first1,
        last1,
        first2,
        last2,
        result,
        stx::less<typename std::iterator_traits<InputIterator1>::value_type,
                  typename std::iterator_traits<InputIterator2>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_SET_INTERSECTION_HPP
